1. Field of the Invention
The present invention relates to a network address forwarding table lookup apparatus and method, and particularly to an Internet Protocol (IP) address lookup apparatus and method with a compression-trie forwarding table.
2. Description of the Related Art
In the recent years, with development of network, it is convenient to transmit data between computers via Internet. A network address, such as an Internet Protocol (IP) address, is applied for recognizing address of a node on Internet. In an Internet node, such as a router, the IP address of data packets transmitted is recognized with a forwarding table, and destination of the data packets is recognized; thus, the data packets will reach their final destination through successive forwarding process.
In conventional network address lookup skill, the concept of network address prefix matching is widely used. Many research works on the forwarding engine of router use the rule of longest prefix matching in address lookup. An example of conventional network address lookup method is shown in FIG. 1. Assume that there is a network environment with network address length equal to 8 bits, and there are four prefix information with format of (prefix/next hop): . . . /1, 0010 . . . /3, 00101011/2, and 10100100/4, where “ . . . ” indicates the “don't care” bit. As shown in FIG. 1, a forwarding table 510 is thus derived from the prefix information, with its memory index order increase from left to right.
In the forwarding table 510, because of the longest prefix matching rule, an incoming data packet with destination address value in the range between 00100000 and 00101111 will be routed to the output port 3, except 00101011; the data packet with destination address 00101011 will be routed to the output port 2; the data packet with destination address 10100100 will be routed to the output port 4; and the data packet with other destination address will be routed to the output port 1. In order to save all output ports of the 8-bit network address (00000000 to 11111111), the forwarding table 510 has 28 entries, with each entry occupies 1 byte (8 bits) memory; thus, the forwarding table 510 for the 8-bit network address occupies 28 bytes memory, which is very large. Therefore, various methods are proposed to achieve smaller forwarding table.
FIG. 2a and FIG. 2b show a compression bit map (CEM) method of the conventional 8-bit network address forwarding table in FIG. 1. CBM forwarding table 520 sets each of the starting entries (network address 00000000, 00100000, 00101011, 00101100, 00110000, 10100100, 10100101) of the range in the forwarding table 510 by bit “1”, and other entries by bit “0”, as shown in FIG. 2a; and a next hop array (NHA) 530 sets the output ports of the starting entries, which occupies 7 bytes in this embodiment. Thus, the CBM forwarding table 520 and the NHA 530 occupies only (28 bits+7 bytes) memory space, which is smaller than the forwarding table 510.
FIG. 3 shows another conventional method of a two-level trie search data structure. In FIG. 3, Each level of the trie has 16 entries and its memory index order increase from left to right. In array 10 for example, the data packet with the first four bits of destination address which locates in ranges of 0000˜0001, 0011˜1001, and 1011˜1111 will be forwarded to the output port 1. Otherwise, it will retrieve pointers B (0010) or C (1010) to do deeper level search. In the second level array 21, which refers to destination address with the first four bits of 0010, the data packet will be forwarded to the output port 3, while an exception of the destination address 00101011 to the output port 2. Similarly, in the second level array 22, which refers to destination address with the first four bits of 1010, the data packet will be forwarded to the output port 1, while an exception of the destination address 10100100 to the output port 4. The two-level trie structure forwarding table occupies 244 bytes memory space in each array, which refers to a total of 3*24 bytes memory in the example.
In Internet, however, data packet forwarding rate should be accelerated for providing higher-speed data transmission services while having smaller forwarding table. In other words, there are two preferred performance requirements of data packet forwarding: small forwarding table size, and fast lookup speed.
As a result, it is an object of the invention to disclose a network address forwarding table lookup apparatus and method that has a fast network address lookup speed with a compact-sized forwarding table.